package MiddlePractice;

import util.TreeNode;

public class Demo450 {
	
//	450. 删除二叉搜索树中的节点
//	给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
	
	public TreeNode deleteNode(TreeNode root, int key) {
		
		if(root.val == key) {
			if(root.left == null) {
				return root.right;
			}
			else if(root.right == null) {
				return root.left;
			}
			else {
				TreeNode target_node = findMinNode(root.right);
				root.val = target_node.val;
				root.right = deleteNode(root.right, target_node.val);
				
			}
		}
		
		else if(root.val > key) {
			root.left = deleteNode(root.left, key);
		}
		
		else {
			root.right =  deleteNode(root.right, key);
		}
		
		return root;
    }

	private TreeNode findMinNode(TreeNode root) {
		
		TreeNode p = root;
		while(p.left != null) {
			p = p.left;
		}
		
		return p;
	}
	
	
}
